1. Field of the Invention
The present invention relates to a method for reliably encoding data streams to be transmitted in various types of communication and computer systems, for example, a one-way satellite broadcast system between a host computer and a subscriber computer.
2. Description of the Related Art
U.S. patent application Ser. No. 08/785,443, which is incorporated herein by reference, discloses a forward error correction (FEC) encoding method for reliably transferring packets of data between a transmitter and receiver in a computer network or communication system. In particular, that patent application provides various packet-level FEC encoding techniques to ensure that large, multimedia data files, including digitized music, still images or moving images, such as may be transmitted by a host computer to one or more receiver subscriber computers using one-way satellite broadcasting, are received error free despite the effects of various types of noise interfering with the transmitted signal.
In many computer networks or communication systems, including the aforementioned one-way satellite broadcast system, the data bits or symbols (such as octets or bytes) are organized into larger groups called packets. When a file is transmitted, uncoded header packets preceding the information-containing packets are sent. Those header packets contain the address and control information to ensure that the following information packets are received by the addressed subscriber computers. Moreover, each packet itself includes uncoded header bytes that indicate, inter alia, to which file the packet belongs and the position of the packet within that file. The remaining bytes of the packet are the body which includes the informational data, such as compressed video data. For example, a packet may be 4,096 bytes long, wherein the header portion is the first 16 bytes, and the body portion is the remaining 4,080 bytes. A large digital object is thus transmitted as a sequence of xe2x80x9coriginalxe2x80x9d or xe2x80x9csourcexe2x80x9d packets.
In the techniques described in U.S. patent application Ser. No. 08/785,443, an extra number of error correcting xe2x80x9cwildcardxe2x80x9d packets are encoded and transmitted with the original packets to provide a predetermined level of protection against packet loss. For example, if a file contains 180 original packets, an extra 20 wildcard packets may be encoded and transmitted with those 180 original packets, as shown in FIG. 1A, to provide against a loss of 20 original packets (approximately an 11% loss). For the reasons described in that patent application, the addressed subscriber computers can successfully reconstruct the large digital object from the received packets so long as any 180 packets, of the 200 packets transmitted, are successfully received.
Additionally, as also described in U.S. patent application Ser. No. 08/785,443, a large file may be broken into smaller xe2x80x9cchunksxe2x80x9d or xe2x80x9csharesxe2x80x9d, each of which generally contains the same number of packets, to allow the large file to be more easily transmitted and received by the system. Each share is individually encoded, transmitted, received and reconstructed (decoded). The file is made whole from the individually constructed shares. As also discussed in that application, the packets of the shares may be interleaved to provide additionally protection against the effects of interfering noise. For example, a data file of 360 original packets and 40 wildcard packets may be divided into two shares of 200 interleaved packets each, as shown in FIG. 1B. Of course, as the files become larger, the number of shares will increase.
As disclosed in U.S. patent application Ser. No. 08/785,443, packet-level error detection processing in the receiving subscriber computers provides an indication that a received packet is xe2x80x9cgoodxe2x80x9d or xe2x80x9cbadxe2x80x9d. Also, an indication is made if a packet has not been received at all, i.e., xe2x80x9clostxe2x80x9d. The bad packets are marked as lost and are not used in further decoding. As further explained therein, as long as the number of lost packets does not exceed the number of wildcard packets, the original packets of the file or share may be completely and correctly reconstructed. Continuing the above examples, for each file or share, at least 180 packets of the 200 transmitted packets must be received as xe2x80x9cgoodxe2x80x9d packets for the successful reconstruction of the original 180 packets. The techniques for decoding the received good packets to reconstruct the original packets are described more fully in U.S. patent application Ser. No. 08/785,443.
In U.S. patent application Ser. No. 09/179,083, the above-described file-oriented packet-level encoding and decoding techniques of U.S. patent application Ser. No. 08/785,443 are extended from data files to data xe2x80x9cstreamsxe2x80x9d. In the computer network/communication system arts, a stream may be a continuous sequence of octets (or bytes) without a packet structure, as in the phrase xe2x80x9cTCP (transmission control protocol) is a stream-based protocolxe2x80x9d. On the other hand, a stream may be a continuous sequence of packets. For example, when those skilled in the art use the phrase xe2x80x9cvideo (or audio) streamingxe2x80x9d, they are usually referring to a stream of UDP/IP (user datagram protocol/internet protocol) or IP Multicast packets. For the present application, a stream is generally any data arriving over a period of time which must be processed and transmitted as it arrives, without waiting for the data to end. Usually, the data is generated by an independent source, and at any given point in time the transmitting system has no knowledge of if or when future data will arrive.
In U.S. patent application Ser. No. 09/179,083, data streams are assembled into xe2x80x9cvirtual filesxe2x80x9d of packets, and then the file-oriented encoding and decoding techniques of U.S. patent application Ser. No. 08/785,443 are applied thereto. That is, the host computer collects the data of the streams into packets, and the packets are collected into a virtual file. The virtual file is then encoded by the host computer using the techniques of U.S. patent application Ser. No. 08/785,443, and the encoded packets are transmitted to the subscriber computers. At the subscriber computer side, the packets are received and collected into a virtual file, which is then decoded using the techniques of U.S. patent application Ser. No. 08/785,443. Once the virtual file is decoded, it is output by the subscriber as a stream of packets, or as a stream of unpacketized data if applicable. However, the method described in U.S. patent application Ser. No. 09/179,083 has a drawback in that delays are created when the host computer waits for data to arrive from the source so it can be packetized and made into a virtual file. Another delay is created as the subscriber computer waits for the arrival of all of the packets required to reconstruct the virtual file. Further, a great deal of memory, and associated read/write operations, is required for storing the virtual file.
Accordingly, to remove these delays from the xe2x80x9cvirtual filexe2x80x9d method of encoding data streams, and to reduce the memory requirements thereof, it would be desirable to encode and decode data streams directly, that is, without the creation of virtual files. However, there are complications when working with data streams as opposed to virtual files. It is usually desirable, or sometimes necessary, to process the data streams in a timely fashion with minimal delays. Such a restriction generally rules out the ability to request retransmission of missed data, and thus, it is important that a reliable encoding scheme for one-way transmission be used. To additionally minimize delays, the host computer should be capable of receiving stream data from the source at a rate similar to the original stream. Moreover, unlike virtual files, when data streams are encoded, there is a lack of knowledge at the host computer, at any given point in time, if and when future data will be coming. This uncertainty of future data must be accounted for in the encoding process. Further, past data may also be unknown, as the host computer may start receiving data from a source in midstream, such as in xe2x80x9clivexe2x80x9d video/audio transmissions.
Accordingly, it would be desirable to provide a method that encodes streams of source packets directly that overcomes the above-described problems. To accomplish this, a method is provided in which, when a packet of data arrives from a source, or a packet is formed from arriving source data bits or octets, the packet""s error-correcting contribution to a group of wildcard packets is computed. Once that computation is done, the packet can then be transmitted to the subscriber computer without waiting for the arrival of any other source packet, thus making the encoding process nearly instantaneous. In particular, advantage is taken of the identity submatrix of the encoding generator matrix described in U.S. patent application Ser. No. 08/785,443, which causes the encoded source packets to be identical to the original source packets. Thus no actual encoding of the source packets is required, and the source packets may be transmitted as soon as the computation of its wildcard contributions has been completed. The contributions from the source packets to each wildcard packet of the group are summed, and when all of the contributions have been computed for all of the wildcard packets associated with the group of source packets, the wildcard packets are transmitted. At the receiver, the source packets may be reconstructed from the received packets using the packet-level decoding techniques set forth in U.S. patent application Ser. No. 08/785,443.
In another aspect of the invention, if a timeout occurs at the host computer because no further stream data is forthcoming, or a signal is received from the source indicating that the data stream has ended, an appropriate set of wildcard packets is transmitted, thus preventing the data stream information from becoming stale. Optionally, the number of wildcards sent, as compared to the total number of wildcards normally computed for the group, may be proportional to the number of source packets actually received by the host computer, as compared to the number of source packets normally received by the host computer when no timeout occurs.